package com.hk.commons.algorithm;

import lombok.Data;
import lombok.RequiredArgsConstructor;

import java.io.Serializable;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Optional;

/**
 * <pre>
 * 单链表数据结构
 *
 * 双向链表数据结构，可参考 {@link  java.util.LinkedList}
 * </pre>
 *
 * @author Kevin
 * @date 2022-07-20 21:59
 */
public class SingleLinked<E> implements Iterable<E>, Serializable {

    /**
     * 头节点
     */
    private Node<E> head;

    public SingleLinked(E head) {
        this.head = new Node<>(head);
    }

    /**
     * 添加元素到下级
     */
    public void add(E next) {
        if (null == head) {
            head = new Node<>(next);
            return;
        }
        var item = head;
        while (true) {
            if (Objects.isNull(item.next)) {
                item.next = new Node<>(next);
                break;
            }
            item = item.next;
        }
    }

    /**
     * 添加元素到头部
     */
    public void addFirst(E first) {
        var node = new Node<>(first);
        node.next = head;
        head = node;
    }

    /**
     * 删除指定的元素
     *
     * @param e 要删除的元素
     */
    public void remove(E e) {
        if (head != null) {
            var item = head;
            if (item.element.equals(e)) {
                item = item.next;
                head = item;
            }
            var next = item.next;
            while (next != null) {
                if (next.element.equals(e)) {
                    item.next = next.next;
                }
                item = item.next;
                next = next.next;
            }
        }
    }

    /**
     * 是否包含指定元素
     */
    public boolean contains(E e) {
        if (Objects.isNull(head)) {
            return Objects.isNull(e);
        }
        var item = head;
        while (item != null) {
            if (item.element.equals(e)) {
                return true;
            }
            item = item.next;
        }
        return false;
    }

    /**
     * 获取链表中倒数第几个节点的元素
     *
     * @param lastIndex 倒数元素的索引值，不能小于1，如果参数大于节点总长度抛出{@link  IndexOutOfBoundsException}
     *                  查询不到元素时返回 empty
     */
    public Optional<E> getNodeByLastIndex(int lastIndex) {
        lastIndex = Math.max(lastIndex, 1);
        var size = size();
        if (lastIndex > size) {
            throw new IndexOutOfBoundsException(lastIndex);
        }
        var temp = head;
        for (int i = 0; i < (size - lastIndex); i++) {
            temp = temp.next;
            if (Objects.isNull(temp)) {
                return Optional.empty();
            }
        }
        return Optional.ofNullable(temp.getElement());
    }

    /**
     * 获取链表的长度(统计头部)
     */
    public int size() {
        if (Objects.isNull(head)) {
            return 0;
        }

        var result = 0;
        var temp = head;
        do {
            result++;
            temp = temp.next;
        } while (temp != null);
        return result;
    }

    /**
     * 单链表的反转
     */
    public void reverse() {
        if (head != null) {
            Node<E> pre = null;
            var current = head;
            var next = current.next;
            while (next != null) {
                current.next = pre;
                pre = current;
                current = next;
                next = next.next;
            }
            current.next = pre;
            head = current;

            //先解决第一个节点写法
//            var current = head;
//            var next = current.next;
//            current.next = null;// 当第一个节点的next置null
//            while (next != null) {
//                var n = next.next;
//                next.next = current;
//                current = next;
//                next = n;
//            }
//            head = current;
        }
    }

//    /**
//     * <pre>
//     * 对链表根据 index分割后，每部分倒序排序，不足 index 个数的部分不变
//     *  如: 假设有个链表:
//     *          4 ->  6 -> 3 -> 12 -> 8 -> 7 -> 10 -> 22
//     *     按3分割后，生成三部分:
//     *          4 ->  6 -> 3
//     *          12 -> 8 -> 7
//     *          10 -> 22
//     *     每部分倒序排序后(不足3的部分不变):
//     *          3 -> 6 -> 4
//     *          7 -> 8 -> 12
//     *          10 -> 22
//     *     最后的结果：
//     *          3 -> 6 -> 4 -> 7 -> 8 -> 12 -> 10 -> 22
//     * </pre>
//     *
//     * @param index 要分割的每部分元素个数
//     */
//    public void reverseByIndex(int index) {
//        Node<E> start = this.head;
//        Node<E> end = getIndexGroupEnd(start, index);
//        if (end != null) {
//            internalReverseByIndex(start, end);
//            Node<E> lastEnd = start;
//            while (lastEnd.next != null) {
//                start = lastEnd.next;
//                end = getIndexGroupEnd(start, index);
//                if (end != null) {
//                    internalReverseByIndex(start, end);
//                    lastEnd.next = end;
//                    lastEnd = start;
//                }
//            }
//            this.head = end;
//        }
//    }
//
//    /**
//     * start: 4 -> 6 -> 3
//     * end: 3 -> 12 -> 8 -> 7 -> 10 -> 22
//     */
//    private void internalReverseByIndex(Node<E> start, Node<E> end) {
//        end = end.next; //12
//        Node<E> pre = null;
//        Node<E> current = start; // 6
//        Node<E> next;
//        while (current != end) {
//            next = current.next;//3
//            current.next = pre;
//            pre = current;
//            current = next;
//        }
//        start.next = end;
//    }
//
//
//    private Node<E> getIndexGroupEnd(Node<E> start, int index) {
//        while (--index != 0 && start != null) {
//            start = start.next;
//        }
//        return start;
//    }

    /**
     * 队列操作: 删除并返回头部元素
     */
    public E poll() {
        var head = this.head;
        if (Objects.isNull(head)) {
            return null;
        }
        var val = head.element;
        this.head = head.next;
        return val;
    }

    /**
     * 队列操作: 返回头部元素，不删除
     */
    public E peek() {
        return Objects.isNull(head) ? null : head.element;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iter(size());
    }

    @Data
    private static class Node<E> {

        /**
         * 当前节点元素值
         */
        private E element;

        /**
         * 当前节点指向的下个节点
         */
        private Node<E> next;

        public Node(E head) {
            this.element = head;
        }
    }

    @RequiredArgsConstructor
    private class Iter implements Iterator<E> {

        private final int size;

        private int nextIndex;

        private Node<E> node;

        @Override
        public boolean hasNext() {
            return nextIndex < size;
        }

        @Override
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            if (Objects.isNull(node)) {
                node = head;
            } else {
                node = node.next;
            }
            nextIndex++;
            return node.element;
        }
    }

}
